package code;

public class MergeSort {
	/*
	 * ������ԣ����Դӹ鲢�㷨���������������O(nlogn)
	 */
	public int mergeSort(int l,int r,int[] array){
		if(l==r){
			return 0;
		}
		int mid=l+r>>1;
		int lcnt=mergeSort(l,mid,array);
		int rcnt=mergeSort(mid+1,r,array);
		int sum=lcnt+rcnt;
		int[] tmp=new int[r-l+1];
		int idx=0;
		int i,j;
		for(i=l,j=mid+1;i<=mid && j<=r;){
			if(array[i]>array[j]){
				sum++;
				tmp[idx++]=array[j];
				j++;
			}
			else{
				tmp[idx++]=array[i];
				i++;
			}
		}
		for(;i<=mid;i++)	tmp[idx++]=array[i];
		for(;j<=r;j++)	tmp[idx++]=array[j];
		for(i=0;i<r-l+1;i++)
			array[l+i]=tmp[i];
		return sum;
	}
	public static void main(String[] args){
		MergeSort ms=new MergeSort();
		int[] array={4,3,7,5,1};
		System.out.println(ms.mergeSort(0, array.length, array));
		for(int i=0;i<array.length;i++){
			System.out.println(array[i]);
		}
	}
}
